 
 #pragma warning( disable : 4786 )  
 
 #include <assert.h>
 #include <set>
 #include <string.h> // memset
 #include <stdio.h> // printf
 #include "NvTriStripObjects.h"
 #include "VertexCache.h"
 
 #define CACHE_INEFFICIENCY 6
 
 NvStripifier::NvStripifier()
 {
     
 }
 
 NvStripifier::~NvStripifier()
 {
     
 }
 
 
 // FindEdgeInfo()
 //
 // find the edge info for these two indices
 //
 NvEdgeInfo * NvStripifier::FindEdgeInfo(NvEdgeInfoVec &edgeInfos, int v0, int v1){
     
     // we can get to it through either array
     // because the edge infos have a v0 and v1
     // and there is no order except how it was
     // first created.
     NvEdgeInfo *infoIter = edgeInfos[v0];
     while (infoIter != NULL){
         if (infoIter->m_v0 == v0){
             if (infoIter->m_v1 == v1)
                 return infoIter;
             else
                 infoIter = infoIter->m_nextV0;
         }
         else {
             assert(infoIter->m_v1 == v0);
             if (infoIter->m_v0 == v1)
                 return infoIter;
             else
                 infoIter = infoIter->m_nextV1;
         }
     }
     return NULL;
 }
 
 
 // FindOtherFace
 //
 // find the other face sharing these vertices
 // exactly like the edge info above
 //
 NvFaceInfo * NvStripifier::FindOtherFace(NvEdgeInfoVec &edgeInfos, int v0, int v1, NvFaceInfo *faceInfo){
     NvEdgeInfo *edgeInfo = FindEdgeInfo(edgeInfos, v0, v1);
 
     if( (edgeInfo == NULL) && (v0 == v1))
     {
         //we've hit a degenerate
         return NULL;
     }
 
     assert(edgeInfo != NULL);
     return (edgeInfo->m_face0 == faceInfo ? edgeInfo->m_face1 : edgeInfo->m_face0);
 }
 
 
 bool NvStripifier::AlreadyExists(NvFaceInfo* faceInfo, NvFaceInfoVec& faceInfos)
 {
     for(size_t i = 0; i < faceInfos.size(); ++i)
     {
         if( (faceInfos[i]->m_v0 == faceInfo->m_v0) &&
             (faceInfos[i]->m_v1 == faceInfo->m_v1) &&
             (faceInfos[i]->m_v2 == faceInfo->m_v2) )
             return true;
     }
 
     return false;
 }
 
 // BuildStripifyInfo()
 //
 // Builds the list of all face and edge infos
 //
 void NvStripifier::BuildStripifyInfo(NvFaceInfoVec &faceInfos, NvEdgeInfoVec &edgeInfos,
                                      const unsigned int maxIndex)
 {
     // reserve space for the face infos, but do not resize them.
     int numIndices = indices.size();
     faceInfos.reserve(numIndices / 3);
     
     // we actually resize the edge infos, so we must initialize to NULL
     edgeInfos.resize(maxIndex + 1);
     for (int i = 0; i < maxIndex + 1; i++)
         edgeInfos[i] = NULL;
     
     // iterate through the triangles of the triangle list
     int numTriangles = numIndices / 3;
     int index        = 0;
     bool bFaceUpdated[3];
 
     for (int i = 0; i < numTriangles; i++)
     {   
         bool bMightAlreadyExist = true;
         bFaceUpdated[0] = false;
         bFaceUpdated[1] = false;
         bFaceUpdated[2] = false;
 
         // grab the indices
         int v0 = indices[index++];
         int v1 = indices[index++];
         int v2 = indices[index++];
 
         //we disregard degenerates
         if(IsDegenerate(v0, v1, v2))
             continue;
         
         // create the face info and add it to the list of faces, but only if this exact face doesn't already 
         //  exist in the list
         NvFaceInfo *faceInfo = new NvFaceInfo(v0, v1, v2);
         
         // grab the edge infos, creating them if they do not already exist
         NvEdgeInfo *edgeInfo01 = FindEdgeInfo(edgeInfos, v0, v1);
         if (edgeInfo01 == NULL)
         {
             //since one of it's edges isn't in the edge data structure, it can't already exist in the face structure
             bMightAlreadyExist = false;
 
             // create the info
             edgeInfo01 = new NvEdgeInfo(v0, v1);
             
             // update the linked list on both 
             edgeInfo01->m_nextV0 = edgeInfos[v0];
             edgeInfo01->m_nextV1 = edgeInfos[v1];
             edgeInfos[v0] = edgeInfo01;
             edgeInfos[v1] = edgeInfo01;
             
             // set face 0
             edgeInfo01->m_face0 = faceInfo;
         }
         else 
         {
             if (edgeInfo01->m_face1 != NULL)
             {
                 printf("BuildStripifyInfo: > 2 triangles on an edge... uncertain consequences\n");
             }
             else
             {
                 edgeInfo01->m_face1 = faceInfo;
                 bFaceUpdated[0] = true;
             }
         }
         
         // grab the edge infos, creating them if they do not already exist
         NvEdgeInfo *edgeInfo12 = FindEdgeInfo(edgeInfos, v1, v2);
         if (edgeInfo12 == NULL)
         {
             bMightAlreadyExist = false;
             
             // create the info
             edgeInfo12 = new NvEdgeInfo(v1, v2);
             
             // update the linked list on both 
             edgeInfo12->m_nextV0 = edgeInfos[v1];
             edgeInfo12->m_nextV1 = edgeInfos[v2];
             edgeInfos[v1] = edgeInfo12;
             edgeInfos[v2] = edgeInfo12;
             
             // set face 0
             edgeInfo12->m_face0 = faceInfo;
         }
         else 
         {
             if (edgeInfo12->m_face1 != NULL)
             {
                 printf("BuildStripifyInfo: > 2 triangles on an edge... uncertain consequences\n");
             }
             else
             {
                 edgeInfo12->m_face1 = faceInfo;
                 bFaceUpdated[1] = true;
             }
         }
         
         // grab the edge infos, creating them if they do not already exist
         NvEdgeInfo *edgeInfo20 = FindEdgeInfo(edgeInfos, v2, v0);
         if (edgeInfo20 == NULL)
         {
             bMightAlreadyExist = false;
 
             // create the info
             edgeInfo20 = new NvEdgeInfo(v2, v0);
             
             // update the linked list on both 
             edgeInfo20->m_nextV0 = edgeInfos[v2];
             edgeInfo20->m_nextV1 = edgeInfos[v0];
             edgeInfos[v2] = edgeInfo20;
             edgeInfos[v0] = edgeInfo20;
             
             // set face 0
             edgeInfo20->m_face0 = faceInfo;
         }
         else 
         {
             if (edgeInfo20->m_face1 != NULL)
             {
                 printf("BuildStripifyInfo: > 2 triangles on an edge... uncertain consequences\n");
             }
             else
             {
                 edgeInfo20->m_face1 = faceInfo;
                 bFaceUpdated[2] = true;
             }
         }
 
         if(bMightAlreadyExist)
         {
             if(!AlreadyExists(faceInfo, faceInfos))
                 faceInfos.push_back(faceInfo);
             else
             {
                 delete faceInfo;
 
                 //cleanup pointers that point to this deleted face
                 if(bFaceUpdated[0])
                     edgeInfo01->m_face1 = NULL;
                 if(bFaceUpdated[1])
                     edgeInfo12->m_face1 = NULL;
                 if(bFaceUpdated[2])
                     edgeInfo20->m_face1 = NULL;
             }
         }
         else
         {
             faceInfos.push_back(faceInfo);
         }
 
     }
 }
 
 
 // FindStartPoint()
 //
 // Finds a good starting point, namely one which has only one neighbor
 //
 int NvStripifier::FindStartPoint(NvFaceInfoVec &faceInfos, NvEdgeInfoVec &edgeInfos)
 {
     int bestCtr = -1;
     int bestIndex = -1;
 
     for(size_t i = 0; i < faceInfos.size(); i++)
     {
         int ctr = 0;
         
         if(FindOtherFace(edgeInfos, faceInfos[i]->m_v0, faceInfos[i]->m_v1, faceInfos[i]) == NULL)
             ctr++;
         if(FindOtherFace(edgeInfos, faceInfos[i]->m_v1, faceInfos[i]->m_v2, faceInfos[i]) == NULL)
             ctr++;
         if(FindOtherFace(edgeInfos, faceInfos[i]->m_v2, faceInfos[i]->m_v0, faceInfos[i]) == NULL)
             ctr++;
         if(ctr > bestCtr)
         {
             bestCtr = ctr;
             bestIndex = i;
             //return i;
         }
     }
     //return -1;
     
     if(bestCtr == 0)
         return -1;
     else
         return bestIndex;
 }
 
 
 // FindGoodResetPoint()
 //  
 // A good reset point is one near other commited areas so that
 // we know that when we've made the longest strips its because
 // we're stripifying in the same general orientation.
 //
 NvFaceInfo* NvStripifier::FindGoodResetPoint(NvFaceInfoVec &faceInfos, NvEdgeInfoVec &edgeInfos){
     // we hop into different areas of the mesh to try to get
     // other large open spans done.  Areas of small strips can
     // just be left to triangle lists added at the end.
     NvFaceInfo *result = NULL;
     
     if(result == NULL)
     {
         int numFaces   = faceInfos.size();
         int startPoint;
         if(bFirstTimeResetPoint)
         {
             //first time, find a face with few neighbors (look for an edge of the mesh)
             startPoint = FindStartPoint(faceInfos, edgeInfos);
             bFirstTimeResetPoint = false;
         }
         else
             startPoint = (int)(((float) numFaces - 1) * meshJump);
         
         if(startPoint == -1)
         {
             startPoint = (int)(((float) numFaces - 1) * meshJump);
             
             //meshJump += 0.1f;
             //if (meshJump > 1.0f)
             //  meshJump = .05f;
         }
 
         int i = startPoint;
         do {
             
             // if this guy isn't visited, try him
             if (faceInfos[i]->m_stripId < 0){
                 result = faceInfos[i];
                 break;
             }
             
             // update the index and clamp to 0-(numFaces-1)
             if (++i >= numFaces)
                 i = 0;
             
         } while (i != startPoint);
         
         // update the meshJump
         meshJump += 0.1f;
         if (meshJump > 1.0f)
             meshJump = .05f;
     }
     
     // return the best face we found
     return result;
 }
 
 
 // GetUniqueVertexInB()
 //
 // Returns the vertex unique to faceB
 //
 int NvStripifier::GetUniqueVertexInB(NvFaceInfo *faceA, NvFaceInfo *faceB){
     
     int facev0 = faceB->m_v0;
     if (facev0 != faceA->m_v0 &&
         facev0 != faceA->m_v1 &&
         facev0 != faceA->m_v2)
         return facev0;
     
     int facev1 = faceB->m_v1;
     if (facev1 != faceA->m_v0 &&
         facev1 != faceA->m_v1 &&
         facev1 != faceA->m_v2)
         return facev1;
     
     int facev2 = faceB->m_v2;
     if (facev2 != faceA->m_v0 &&
         facev2 != faceA->m_v1 &&
         facev2 != faceA->m_v2)
         return facev2;
     
     // nothing is different
     return -1;
 }
 
 
 // GetSharedVertices()
 //
 // Returns the (at most) two vertices shared between the two faces
 //
 void NvStripifier::GetSharedVertices(NvFaceInfo *faceA, NvFaceInfo *faceB, int* vertex0, int* vertex1)
 {
     *vertex0 = -1;
     *vertex1 = -1;
 
     int facev0 = faceB->m_v0;
     if (facev0 == faceA->m_v0 ||
         facev0 == faceA->m_v1 ||
         facev0 == faceA->m_v2)
     {
         if(*vertex0 == -1)
             *vertex0 = facev0;
         else
         {
             *vertex1 = facev0;
             return;
         }
     }
     
     int facev1 = faceB->m_v1;
     if (facev1 == faceA->m_v0 ||
         facev1 == faceA->m_v1 ||
         facev1 == faceA->m_v2)
     {
         if(*vertex0 == -1)
             *vertex0 = facev1;
         else
         {
             *vertex1 = facev1;
             return;
         }
     }   
 
     int facev2 = faceB->m_v2;
     if (facev2 == faceA->m_v0 ||
         facev2 == faceA->m_v1 ||
         facev2 == faceA->m_v2)
     {
         if(*vertex0 == -1)
             *vertex0 = facev2;
         else
         {
             *vertex1 = facev2;
             return;
         }
     }
 
 }
 
 
 // GetNextIndex()
 //
 // Returns vertex of the input face which is "next" in the input index list
 //
 inline int NvStripifier::GetNextIndex(const WordVec &indices, NvFaceInfo *face){
     
     int numIndices = indices.size();
     assert(numIndices >= 2);
     
     int v0  = indices[numIndices-2];
     int v1  = indices[numIndices-1];
     
     int fv0 = face->m_v0;
     int fv1 = face->m_v1;
     int fv2 = face->m_v2;
     
     if (fv0 != v0 && fv0 != v1){
         if ((fv1 != v0 && fv1 != v1) || (fv2 != v0 && fv2 != v1)){
             printf("GetNextIndex: Triangle doesn't have all of its vertices\n");
             printf("GetNextIndex: Duplicate triangle probably got us derailed\n");
         }
         return fv0;
     }
     if (fv1 != v0 && fv1 != v1){
         if ((fv0 != v0 && fv0 != v1) || (fv2 != v0 && fv2 != v1)){
             printf("GetNextIndex: Triangle doesn't have all of its vertices\n");
             printf("GetNextIndex: Duplicate triangle probably got us derailed\n");
         }
         return fv1;
     }
     if (fv2 != v0 && fv2 != v1){
         if ((fv0 != v0 && fv0 != v1) || (fv1 != v0 && fv1 != v1)){
             printf("GetNextIndex: Triangle doesn't have all of its vertices\n");
             printf("GetNextIndex: Duplicate triangle probably got us derailed\n");
         }
         return fv2;
     }
     
     // shouldn't get here, but let's try and fail gracefully
     if( (fv0 == fv1) || (fv0 == fv2) )
         return fv0;
     else if( (fv1 == fv0) || (fv1 == fv2) )
         return fv1;
     else if( (fv2 == fv0) || (fv2 == fv1) )
         return fv2;
     else
         return -1;
 }
 
 
 // IsMarked()
 //
 // If either the faceInfo has a real strip index because it is
 // already assign to a committed strip OR it is assigned in an
 // experiment and the experiment index is the one we are building
 // for, then it is marked and unavailable
 inline bool NvStripInfo::IsMarked(NvFaceInfo *faceInfo){
     return (faceInfo->m_stripId >= 0) || (IsExperiment() && faceInfo->m_experimentId == m_experimentId);
 }
 
 
 // MarkTriangle()
 //
 // Marks the face with the current strip ID
 //
 inline void NvStripInfo::MarkTriangle(NvFaceInfo *faceInfo){
     assert(!IsMarked(faceInfo));
     if (IsExperiment()){
         faceInfo->m_experimentId = m_experimentId;
         faceInfo->m_testStripId  = m_stripId;
     }
     else{
         assert(faceInfo->m_stripId == -1);
         faceInfo->m_experimentId = -1;
         faceInfo->m_stripId      = m_stripId;
     }
 }
 
 
 bool NvStripInfo::Unique(NvFaceInfoVec& faceVec, NvFaceInfo* face)
 {
     bool bv0, bv1, bv2; //bools to indicate whether a vertex is in the faceVec or not
     bv0 = bv1 = bv2 = false;
 
     for(size_t i = 0; i < faceVec.size(); i++)
     {
         if(!bv0)
         {
             if( (faceVec[i]->m_v0 == face->m_v0) || 
                 (faceVec[i]->m_v1 == face->m_v0) ||
                 (faceVec[i]->m_v2 == face->m_v0) )
                 bv0 = true;
         }
 
         if(!bv1)
         {
             if( (faceVec[i]->m_v0 == face->m_v1) || 
                 (faceVec[i]->m_v1 == face->m_v1) ||
                 (faceVec[i]->m_v2 == face->m_v1) )
                 bv1 = true;
         }
 
         if(!bv2)
         {
             if( (faceVec[i]->m_v0 == face->m_v2) || 
                 (faceVec[i]->m_v1 == face->m_v2) ||
                 (faceVec[i]->m_v2 == face->m_v2) )
                 bv2 = true;
         }
 
         //the face is not unique, all it's vertices exist in the face vector
         if(bv0 && bv1 && bv2)
             return false;
     }
     
     //if we get out here, it's unique
     return true;
 }
 
 
 // Build()
 //
 // Builds a strip forward as far as we can go, then builds backwards, and joins the two lists
 //
 void NvStripInfo::Build(NvEdgeInfoVec &edgeInfos, NvFaceInfoVec &faceInfos)
 {
     // used in building the strips forward and backward
     WordVec scratchIndices;
     
     // build forward... start with the initial face
     NvFaceInfoVec forwardFaces, backwardFaces;
     forwardFaces.push_back(m_startInfo.m_startFace);
 
     MarkTriangle(m_startInfo.m_startFace);
     
     int v0 = (m_startInfo.m_toV1 ? m_startInfo.m_startEdge->m_v0 : m_startInfo.m_startEdge->m_v1);
     int v1 = (m_startInfo.m_toV1 ? m_startInfo.m_startEdge->m_v1 : m_startInfo.m_startEdge->m_v0);
     
     // easiest way to get v2 is to use this function which requires the
     // other indices to already be in the list.
     scratchIndices.push_back(v0);
     scratchIndices.push_back(v1);
     int v2 = NvStripifier::GetNextIndex(scratchIndices, m_startInfo.m_startFace);
     scratchIndices.push_back(v2);
 
     //
     // build the forward list
     //
     int nv0 = v1;
     int nv1 = v2;
 
     NvFaceInfo *nextFace = NvStripifier::FindOtherFace(edgeInfos, nv0, nv1, m_startInfo.m_startFace);
     while (nextFace != NULL && !IsMarked(nextFace))
     {
         //check to see if this next face is going to cause us to die soon
         int testnv0 = nv1;
         int testnv1 = NvStripifier::GetNextIndex(scratchIndices, nextFace);
         
         NvFaceInfo* nextNextFace = NvStripifier::FindOtherFace(edgeInfos, testnv0, testnv1, nextFace);
 
         if( (nextNextFace == NULL) || (IsMarked(nextNextFace)) )
         {
             //uh, oh, we're following a dead end, try swapping
             NvFaceInfo* testNextFace = NvStripifier::FindOtherFace(edgeInfos, nv0, testnv1, nextFace);
 
             if( ((testNextFace != NULL) && !IsMarked(testNextFace)) )
             {
                 //we only swap if it buys us something
                 
                 //add a "fake" degenerate face
                 NvFaceInfo* tempFace = new NvFaceInfo(nv0, nv1, nv0, true);
                 
                 forwardFaces.push_back(tempFace);
                 MarkTriangle(tempFace);
 
                 scratchIndices.push_back(nv0);
                 testnv0 = nv0;
 
                 ++m_numDegenerates;
             }
 
         }
 
         // add this to the strip
         forwardFaces.push_back(nextFace);
 
         MarkTriangle(nextFace);
         
         // add the index
         //nv0 = nv1;
         //nv1 = NvStripifier::GetNextIndex(scratchIndices, nextFace);
         scratchIndices.push_back(testnv1);
         
         // and get the next face
         nv0 = testnv0;
         nv1 = testnv1;
 
         nextFace = NvStripifier::FindOtherFace(edgeInfos, nv0, nv1, nextFace);
     
     }
     
     // tempAllFaces is going to be forwardFaces + backwardFaces
     // it's used for Unique()
     NvFaceInfoVec tempAllFaces;
     for(size_t i = 0; i < forwardFaces.size(); i++)
         tempAllFaces.push_back(forwardFaces[i]);
 
     //
     // reset the indices for building the strip backwards and do so
     //
     scratchIndices.resize(0);
     scratchIndices.push_back(v2);
     scratchIndices.push_back(v1);
     scratchIndices.push_back(v0);
     nv0 = v1;
     nv1 = v0;
     nextFace = NvStripifier::FindOtherFace(edgeInfos, nv0, nv1, m_startInfo.m_startFace);
     while (nextFace != NULL && !IsMarked(nextFace))
     {
         //this tests to see if a face is "unique", meaning that its vertices aren't already in the list
         // so, strips which "wrap-around" are not allowed
         if(!Unique(tempAllFaces, nextFace))
             break;
 
         //check to see if this next face is going to cause us to die soon
         int testnv0 = nv1;
         int testnv1 = NvStripifier::GetNextIndex(scratchIndices, nextFace);
         
         NvFaceInfo* nextNextFace = NvStripifier::FindOtherFace(edgeInfos, testnv0, testnv1, nextFace);
 
         if( (nextNextFace == NULL) || (IsMarked(nextNextFace)) )
         {
             //uh, oh, we're following a dead end, try swapping
             NvFaceInfo* testNextFace = NvStripifier::FindOtherFace(edgeInfos, nv0, testnv1, nextFace);
             if( ((testNextFace != NULL) && !IsMarked(testNextFace)) )
             {
                 //we only swap if it buys us something
                 
                 //add a "fake" degenerate face
                 NvFaceInfo* tempFace = new NvFaceInfo(nv0, nv1, nv0, true);
 
                 backwardFaces.push_back(tempFace);
                 MarkTriangle(tempFace);
                 scratchIndices.push_back(nv0);
                 testnv0 = nv0;
 
                 ++m_numDegenerates;
             }
                 
         }
 
         // add this to the strip
         backwardFaces.push_back(nextFace);
         
         //this is just so Unique() will work
         tempAllFaces.push_back(nextFace);
 
         MarkTriangle(nextFace);
         
         // add the index
         //nv0 = nv1;
         //nv1 = NvStripifier::GetNextIndex(scratchIndices, nextFace);
         scratchIndices.push_back(testnv1);
         
         // and get the next face
         nv0 = testnv0;
         nv1 = testnv1;
         nextFace = NvStripifier::FindOtherFace(edgeInfos, nv0, nv1, nextFace);
     }
     
     // Combine the forward and backwards stripification lists and put into our own face vector
     Combine(forwardFaces, backwardFaces);
 }
 
 
 // Combine()
 //
 // Combines the two input face vectors and puts the result into m_faces
 //
 void NvStripInfo::Combine(const NvFaceInfoVec &forward, const NvFaceInfoVec &backward){
     
     // add backward faces
     int numFaces = backward.size();
     for (int i = numFaces - 1; i >= 0; i--)
         m_faces.push_back(backward[i]);
     
     // add forward faces
     numFaces = forward.size();
     for (int i = 0; i < numFaces; i++)
         m_faces.push_back(forward[i]);
 }
 
 
 // SharesEdge()
 //
 // Returns true if the input face and the current strip share an edge
 //
 bool NvStripInfo::SharesEdge(const NvFaceInfo* faceInfo, NvEdgeInfoVec &edgeInfos)
 {
     //check v0->v1 edge
     NvEdgeInfo* currEdge = NvStripifier::FindEdgeInfo(edgeInfos, faceInfo->m_v0, faceInfo->m_v1);
     
     if(IsInStrip(currEdge->m_face0) || IsInStrip(currEdge->m_face1))
         return true;
     
     //check v1->v2 edge
     currEdge = NvStripifier::FindEdgeInfo(edgeInfos, faceInfo->m_v1, faceInfo->m_v2);
     
     if(IsInStrip(currEdge->m_face0) || IsInStrip(currEdge->m_face1))
         return true;
     
     //check v2->v0 edge
     currEdge = NvStripifier::FindEdgeInfo(edgeInfos, faceInfo->m_v2, faceInfo->m_v0);
     
     if(IsInStrip(currEdge->m_face0) || IsInStrip(currEdge->m_face1))
         return true;
     
     return false;
     
 }
 
 
 // CommitStrips()
 //
 // "Commits" the input strips by setting their m_experimentId to -1 and adding to the allStrips
 //  vector
 //
 void NvStripifier::CommitStrips(NvStripInfoVec &allStrips, const NvStripInfoVec &strips)
 {   
     // Iterate through strips
     int numStrips = strips.size();
     for (int i = 0; i < numStrips; i++){
 
         // Tell the strip that it is now real
         NvStripInfo *strip = strips[i];
         strip->m_experimentId = -1;
         
         // add to the list of real strips
         allStrips.push_back(strip);
         
         // Iterate through the faces of the strip
         // Tell the faces of the strip that they belong to a real strip now
         const NvFaceInfoVec &faces = strips[i]->m_faces;
         int numFaces = faces.size();
 
         for (int j = 0; j < numFaces; j++)
         {
             strip->MarkTriangle(faces[j]);
         }
     }
 }
 
 
 // FindTraversal()
 //
 // Finds the next face to start the next strip on.
 //
 bool NvStripifier::FindTraversal(NvFaceInfoVec &faceInfos,
                                  NvEdgeInfoVec    &edgeInfos,
                                  NvStripInfo      *strip,
                                  NvStripStartInfo &startInfo){
     
     // if the strip was v0->v1 on the edge, then v1 will be a vertex in the next edge.
     int v = (strip->m_startInfo.m_toV1 ? strip->m_startInfo.m_startEdge->m_v1 : strip->m_startInfo.m_startEdge->m_v0);
     
     NvFaceInfo *untouchedFace = NULL;
     NvEdgeInfo *edgeIter      = edgeInfos[v];
     while (edgeIter != NULL){
         NvFaceInfo *face0 = edgeIter->m_face0;
         NvFaceInfo *face1 = edgeIter->m_face1;
         if ((face0 != NULL && !strip->IsInStrip(face0)) && face1 != NULL && !strip->IsMarked(face1))
         {
             untouchedFace = face1;
             break;
         }
         if ((face1 != NULL && !strip->IsInStrip(face1)) && face0 != NULL && !strip->IsMarked(face0)){
             untouchedFace = face0;
             break;
         }
         
         // find the next edgeIter
         edgeIter = (edgeIter->m_v0 == v ? edgeIter->m_nextV0 : edgeIter->m_nextV1);
     }
     
     startInfo.m_startFace = untouchedFace;
     startInfo.m_startEdge = edgeIter;
     if (edgeIter != NULL)
     {
         if(strip->SharesEdge(startInfo.m_startFace, edgeInfos))
             startInfo.m_toV1 = (edgeIter->m_v0 == v);  //note! used to be m_v1
         else
             startInfo.m_toV1 = (edgeIter->m_v1 == v);
     }
     return (startInfo.m_startFace != NULL);
 }
 
 
 // RemoveSmallStrips()
 //
 // allStrips is the whole strip vector...all small strips will be deleted from this list, to avoid leaking mem
 // allBigStrips is an out parameter which will contain all strips above minStripLength
 // faceList is an out parameter which will contain all faces which were removed from the striplist
 //
 void NvStripifier::RemoveSmallStrips(NvStripInfoVec& allStrips, NvStripInfoVec& allBigStrips, NvFaceInfoVec& faceList)
 {
     faceList.clear();
     allBigStrips.clear();  //make sure these are empty
     NvFaceInfoVec tempFaceList;
     
     for(size_t i = 0; i < allStrips.size(); i++)
     {
         if(allStrips[i]->m_faces.size() < size_t(minStripLength))
         {
             //strip is too small, add faces to faceList
             for(size_t j = 0; j < allStrips[i]->m_faces.size(); j++)
                 tempFaceList.push_back(allStrips[i]->m_faces[j]);
             
             //and free memory
             delete allStrips[i];
         }
         else
         {
             allBigStrips.push_back(allStrips[i]);
         }
     }
     
     if(tempFaceList.size())
     {
         bool *bVisitedList = new bool[tempFaceList.size()];
         memset(bVisitedList, 0, tempFaceList.size()*sizeof(bool));
         
         VertexCache* vcache = new VertexCache(cacheSize);
         
         int bestNumHits = -1;
         int numHits;
         int bestIndex = -1;
         
         while(1)
         {
             bestNumHits = -1;
             
             //find best face to add next, given the current cache
             for(size_t i = 0; i < tempFaceList.size(); i++)
             {
                 if(bVisitedList[i])
                     continue;
                 
                 numHits = CalcNumHitsFace(vcache, tempFaceList[i]);
                 if(numHits > bestNumHits)
                 {
                     bestNumHits = numHits;
                     bestIndex = i;
                 }
             }
             
             if(bestNumHits == -1.0f)
                 break;
             bVisitedList[bestIndex] = true;
             UpdateCacheFace(vcache, tempFaceList[bestIndex]);
             faceList.push_back(tempFaceList[bestIndex]);
         }
         
         delete vcache;
         delete[] bVisitedList;
     }
 }
 
 
 // NextIsCW()
 //
 // Returns true if the next face should be ordered in CW fashion
 //
 bool NvStripifier::NextIsCW(const int numIndices)
 {
     return ((numIndices % 2) == 0);
 }
 
 
 // IsCW()
 //
 // Returns true if the face is ordered in CW fashion
 //
 bool NvStripifier::IsCW(NvFaceInfo *faceInfo, int v0, int v1)
 {
     if (faceInfo->m_v0 == v0)
         return (faceInfo->m_v1 == v1);
     
     else if (faceInfo->m_v1 == v0)
         return (faceInfo->m_v2 == v1);
     
     else 
         return (faceInfo->m_v0 == v1);
     
     // shouldn't get here
     assert(0);
     return false;
 }
 
 bool NvStripifier::FaceContainsIndex(const NvFaceInfo& face, const unsigned int index)
 {
     return ( (size_t(face.m_v0) == index) || (size_t(face.m_v1) == index) || (size_t(face.m_v2) == index) );
 }
 
 bool NvStripifier::IsMoneyFace(const NvFaceInfo& face)
 {
     if(FaceContainsIndex(face, 800) &&
        FaceContainsIndex(face, 812) &&
        FaceContainsIndex(face, 731))
        return true;
 
     return false;
 }
                 
 // CreateStrips()
 //
 // Generates actual strips from the list-in-strip-order.
 //
 void NvStripifier::CreateStrips(const NvStripInfoVec& allStrips, IntVec& stripIndices, 
                                 const bool bStitchStrips, unsigned int& numSeparateStrips, 
                                 const bool bRestart, const unsigned int restartVal)
 {
     assert(numSeparateStrips == 0);
 
     NvFaceInfo tLastFace(0, 0, 0);
     NvFaceInfo tPrevStripLastFace(0, 0, 0);
     int nStripCount = allStrips.size();
     assert(nStripCount > 0);
 
     //we infer the cw/ccw ordering depending on the number of indices
     //this is screwed up by the fact that we insert -1s to denote changing strips
     //this is to account for that
     int accountForNegatives = 0;
 
     for (int i = 0; i < nStripCount; i++)
     {
         NvStripInfo *strip = allStrips[i];
         int nStripFaceCount = strip->m_faces.size();
         assert(nStripFaceCount > 0);
 
         // Handle the first face in the strip
         {
             NvFaceInfo tFirstFace(strip->m_faces[0]->m_v0, strip->m_faces[0]->m_v1, strip->m_faces[0]->m_v2);
 
             // If there is a second face, reorder vertices such that the
             // unique vertex is first
             if (nStripFaceCount > 1)
             {
                 int nUnique = NvStripifier::GetUniqueVertexInB(strip->m_faces[1], &tFirstFace);
                 if (nUnique == tFirstFace.m_v1)
                 {
                     SWAP(tFirstFace.m_v0, tFirstFace.m_v1);
                 }
                 else if (nUnique == tFirstFace.m_v2)
                 {
                     SWAP(tFirstFace.m_v0, tFirstFace.m_v2);
                 }
 
                 // If there is a third face, reorder vertices such that the
                 // shared vertex is last
                 if (nStripFaceCount > 2)
                 {
                     if(IsDegenerate(strip->m_faces[1]))
                     {
                         int pivot = strip->m_faces[1]->m_v1;
                         if(tFirstFace.m_v1 == pivot)
                         {
                             SWAP(tFirstFace.m_v1, tFirstFace.m_v2);
                         }
                     }
                     else
                     {
                         int nShared0, nShared1;
                         GetSharedVertices(strip->m_faces[2], &tFirstFace, &nShared0, &nShared1);
                         if ( (nShared0 == tFirstFace.m_v1) && (nShared1 == -1) )
                         {
                             SWAP(tFirstFace.m_v1, tFirstFace.m_v2);
                         }
                     }
                 }
             }
 
             if( (i == 0) || !bStitchStrips || bRestart)
             {
                 if(!IsCW(strip->m_faces[0], tFirstFace.m_v0, tFirstFace.m_v1))
                     stripIndices.push_back(tFirstFace.m_v0);
             }
             else
             {
                 // Double tap the first in the new strip
                 stripIndices.push_back(tFirstFace.m_v0);
     
                 // Check CW/CCW ordering
                 if (NextIsCW(stripIndices.size() - accountForNegatives) != IsCW(strip->m_faces[0], tFirstFace.m_v0, tFirstFace.m_v1))
                 {
                     stripIndices.push_back(tFirstFace.m_v0);
                 }
             }
 
             stripIndices.push_back(tFirstFace.m_v0);
             stripIndices.push_back(tFirstFace.m_v1);
             stripIndices.push_back(tFirstFace.m_v2);
 
             // Update last face info
             tLastFace = tFirstFace;
         }
 
         for (int j = 1; j < nStripFaceCount; j++)
         {
             int nUnique = GetUniqueVertexInB(&tLastFace, strip->m_faces[j]);
             if (nUnique != -1)
             {
                 stripIndices.push_back(nUnique);
 
                 // Update last face info
                 tLastFace.m_v0 = tLastFace.m_v1;
                 tLastFace.m_v1 = tLastFace.m_v2;
                 tLastFace.m_v2 = nUnique;
             }
             else
             {
                 //we've hit a degenerate
                 stripIndices.push_back(strip->m_faces[j]->m_v2);
                 tLastFace.m_v0 = strip->m_faces[j]->m_v0;//tLastFace.m_v1;
                 tLastFace.m_v1 = strip->m_faces[j]->m_v1;//tLastFace.m_v2;
                 tLastFace.m_v2 = strip->m_faces[j]->m_v2;//tLastFace.m_v1;
 
             }
         }
 
         // Double tap between strips.
         if (bStitchStrips && !bRestart) 
         {
             if (i != nStripCount - 1)
                 stripIndices.push_back(tLastFace.m_v2);
         } 
         else if (bRestart) 
         {
             stripIndices.push_back(restartVal);
         } 
         else 
         {
             //-1 index indicates next strip
             stripIndices.push_back(-1);
             accountForNegatives++;
             numSeparateStrips++;
         }
 
         // Update last face info
         tLastFace.m_v0 = tLastFace.m_v1;
         tLastFace.m_v1 = tLastFace.m_v2;
         tLastFace.m_v2 = tLastFace.m_v2;
     }
     
     if(bStitchStrips || bRestart)
         numSeparateStrips = 1;
 }
 
 
 // Stripify()
 //
 //
 // in_indices are the input indices of the mesh to stripify
 // in_cacheSize is the target cache size 
 //
 void NvStripifier::Stripify(const WordVec &in_indices, const int in_cacheSize, 
                             const int in_minStripLength, const unsigned int maxIndex, 
                             NvStripInfoVec &outStrips, NvFaceInfoVec& outFaceList)
 {
     meshJump = 0.0f;
     bFirstTimeResetPoint = true; //used in FindGoodResetPoint()
 
     //the number of times to run the experiments
     int numSamples = 10;
     
     //the cache size, clamped to one
     if ( in_cacheSize - CACHE_INEFFICIENCY < 1 ) cacheSize = 1;
     else cacheSize = in_cacheSize - CACHE_INEFFICIENCY;
     
     minStripLength = in_minStripLength;  //this is the strip size threshold below which we dump the strip into a list
     
     indices = in_indices;
     
     // build the stripification info
     NvFaceInfoVec allFaceInfos;
     NvEdgeInfoVec allEdgeInfos;
     
     BuildStripifyInfo(allFaceInfos, allEdgeInfos, maxIndex);
     
     NvStripInfoVec allStrips;
 
     // stripify
     FindAllStrips(allStrips, allFaceInfos, allEdgeInfos, numSamples);
 
     //split up the strips into cache friendly pieces, optimize them, then dump these into outStrips
     SplitUpStripsAndOptimize(allStrips, outStrips, allEdgeInfos, outFaceList);
 
     //clean up
     for(size_t i = 0; i < allStrips.size(); i++)
     {
         delete allStrips[i];
     }
     
     for (size_t i = 0; i < allEdgeInfos.size(); i++)
     {
         NvEdgeInfo *info = allEdgeInfos[i];
         while (info != NULL)
         {
             NvEdgeInfo *next = (size_t(info->m_v0) == i ? info->m_nextV0 : info->m_nextV1);
             info->Unref();
             info = next;
         }
     }
     
 }
 
 
 bool NvStripifier::IsDegenerate(const NvFaceInfo* face)
 {
     if(face->m_v0 == face->m_v1)
         return true;
     else if(face->m_v0 == face->m_v2)
         return true;
     else if(face->m_v1 == face->m_v2)
         return true;
     else
         return false;
 }
 
 bool NvStripifier::IsDegenerate(const unsigned int v0, const unsigned int v1, const unsigned int v2)
 {
     if(v0 == v1)
         return true;
     else if(v0 == v2)
         return true;
     else if(v1 == v2)
         return true;
     else
         return false;
 }
 
 // SplitUpStripsAndOptimize()
 //
 // Splits the input vector of strips (allBigStrips) into smaller, cache friendly pieces, then
 //  reorders these pieces to maximize cache hits
 // The final strips are output through outStrips
 //
 void NvStripifier::SplitUpStripsAndOptimize(NvStripInfoVec &allStrips, NvStripInfoVec &outStrips,
                                             NvEdgeInfoVec& edgeInfos, NvFaceInfoVec& outFaceList)
 {
     int threshold = cacheSize;
     NvStripInfoVec tempStrips;
     
     //split up strips into threshold-sized pieces
     for(size_t i = 0; i < allStrips.size(); i++)
     {
         NvStripInfo* currentStrip;
         NvStripStartInfo startInfo(NULL, NULL, false);
     
         int actualStripSize = 0;
         for(size_t j = 0; j < allStrips[i]->m_faces.size(); ++j)
         {
             if( !IsDegenerate(allStrips[i]->m_faces[j]) )
                 actualStripSize++;
         }
         
         if(actualStripSize /*allStrips[i]->m_faces.size()*/ > threshold)
         {
             
             int numTimes    = actualStripSize /*allStrips[i]->m_faces.size()*/ / threshold;
             int numLeftover = actualStripSize /*allStrips[i]->m_faces.size()*/ % threshold;
 
             int degenerateCount = 0;
             int j;
             for(j = 0; j < numTimes; j++)
             {
                 currentStrip = new NvStripInfo(startInfo, 0, -1);
                 
                 int faceCtr = j*threshold + degenerateCount;
                 bool bFirstTime = true;
                 while(faceCtr < threshold+(j*threshold)+degenerateCount)
                 {
                     if(IsDegenerate(allStrips[i]->m_faces[faceCtr]))
                     {
                         degenerateCount++;
                         
                         //last time or first time through, no need for a degenerate
                         if( (((faceCtr + 1) != threshold+(j*threshold)+degenerateCount) ||
                              ((j == numTimes - 1) && (numLeftover < 4) && (numLeftover > 0))) && 
                              !bFirstTime)
                         {
                             currentStrip->m_faces.push_back(allStrips[i]->m_faces[faceCtr++]);
                         }
                         else
                         {
                             //but, we do need to delete the degenerate, if it's marked fake, to avoid leaking
                             if(allStrips[i]->m_faces[faceCtr]->m_bIsFake)
                             {
                                 delete allStrips[i]->m_faces[faceCtr], allStrips[i]->m_faces[faceCtr] = NULL;
                             }
                             ++faceCtr;
                         }
                     }
                     else
                     {
                         currentStrip->m_faces.push_back(allStrips[i]->m_faces[faceCtr++]);
                         bFirstTime = false;
                     }
                 }
                 /*
                 for(int faceCtr = j*threshold; faceCtr < threshold+(j*threshold); faceCtr++)
                 {
                     currentStrip->m_faces.push_back(allStrips[i]->m_faces[faceCtr]);
                 }
                 */
                 if(j == numTimes - 1) //last time through
                 {
                     if( (numLeftover < 4) && (numLeftover > 0) ) //way too small
                     {
                         //just add to last strip
                         int ctr = 0;
                         while(ctr < numLeftover)
                         {
                             IsDegenerate( allStrips[i]->m_faces[faceCtr] ) ? ++degenerateCount : ++ctr;
                             currentStrip->m_faces.push_back(allStrips[i]->m_faces[faceCtr++]);
                         }
                         numLeftover = 0;
                     }
                 }
                 tempStrips.push_back(currentStrip);
             }
             
             int leftOff = j * threshold + degenerateCount;
             
             if(numLeftover != 0)
             {
                 currentStrip = new NvStripInfo(startInfo, 0, -1);   
                 
                 int ctr = 0;
                 bool bFirstTime = true;
                 while(ctr < numLeftover)
                 {
                     if( !IsDegenerate(allStrips[i]->m_faces[leftOff]) )
                     {
                         ctr++;
                         bFirstTime = false;
                         currentStrip->m_faces.push_back(allStrips[i]->m_faces[leftOff++]);
                     }
                     else if(!bFirstTime)
                         currentStrip->m_faces.push_back(allStrips[i]->m_faces[leftOff++]);
                     else
                     {
                         //don't leak
                         if(allStrips[i]->m_faces[leftOff]->m_bIsFake)
                         {
                             delete allStrips[i]->m_faces[leftOff], allStrips[i]->m_faces[leftOff] = NULL;
                         }
 
                         leftOff++;
                     }
                 }
                 /*
                 for(int k = 0; k < numLeftover; k++)
                 {
                     currentStrip->m_faces.push_back(allStrips[i]->m_faces[leftOff++]);
                 }
                 */
                 
                 tempStrips.push_back(currentStrip);
             }
         }
         else
         {
             //we're not just doing a tempStrips.push_back(allBigStrips[i]) because
             // this way we can delete allBigStrips later to free the memory
             currentStrip = new NvStripInfo(startInfo, 0, -1);
             
             for(size_t j = 0; j < allStrips[i]->m_faces.size(); j++)
                 currentStrip->m_faces.push_back(allStrips[i]->m_faces[j]);
             
             tempStrips.push_back(currentStrip);
         }
     }
 
     //add small strips to face list
     NvStripInfoVec tempStrips2;
     RemoveSmallStrips(tempStrips, tempStrips2, outFaceList);
     
     outStrips.clear();
     //screw optimization for now
 //  for(i = 0; i < tempStrips.size(); ++i)
 //    outStrips.push_back(tempStrips[i]);
     
     if(tempStrips2.size() != 0)
     {
         //Optimize for the vertex cache
         VertexCache* vcache = new VertexCache(cacheSize);
         
         float bestNumHits = -1.0f;
         float numHits;
         int bestIndex = -1;
         //bool done = false;
         
         int firstIndex = 0;
         float minCost = 10000.0f;
         
         for(size_t i = 0; i < tempStrips2.size(); i++)
         {
             int numNeighbors = 0;
             
             //find strip with least number of neighbors per face
             for(size_t j = 0; j < tempStrips2[i]->m_faces.size(); j++)
             {
                 numNeighbors += NumNeighbors(tempStrips2[i]->m_faces[j], edgeInfos);
             }
             
             float currCost = (float)numNeighbors / (float)tempStrips2[i]->m_faces.size();
             if(currCost < minCost)
             {
                 minCost = currCost;
                 firstIndex = i;
             }
         }
         
         UpdateCacheStrip(vcache, tempStrips2[firstIndex]);
         outStrips.push_back(tempStrips2[firstIndex]);
         
         tempStrips2[firstIndex]->visited = true;
         
         bool bWantsCW = (tempStrips2[firstIndex]->m_faces.size() % 2) == 0;
 
         //this n^2 algo is what slows down stripification so much....
         // needs to be improved
         while(1)
         {
             bestNumHits = -1.0f;
             
             //find best strip to add next, given the current cache
             for(size_t i = 0; i < tempStrips2.size(); i++)
             {
                 if(tempStrips2[i]->visited)
                     continue;
 
                 numHits = CalcNumHitsStrip(vcache, tempStrips2[i]);
                 if(numHits > bestNumHits)
                 {
                     bestNumHits = numHits;
                     bestIndex = i;
                 }
                 else if(numHits >= bestNumHits)
                 {
                     //check previous strip to see if this one requires it to switch polarity
                     NvStripInfo *strip = tempStrips2[i];
                     int nStripFaceCount = strip->m_faces.size();
                     
                     NvFaceInfo tFirstFace(strip->m_faces[0]->m_v0, strip->m_faces[0]->m_v1, strip->m_faces[0]->m_v2);
                     
                     // If there is a second face, reorder vertices such that the
                     // unique vertex is first
                     if (nStripFaceCount > 1)
                     {
                         int nUnique = NvStripifier::GetUniqueVertexInB(strip->m_faces[1], &tFirstFace);
                         if (nUnique == tFirstFace.m_v1)
                         {
                             SWAP(tFirstFace.m_v0, tFirstFace.m_v1);
                         }
                         else if (nUnique == tFirstFace.m_v2)
                         {
                             SWAP(tFirstFace.m_v0, tFirstFace.m_v2);
                         }
                         
                         // If there is a third face, reorder vertices such that the
                         // shared vertex is last
                         if (nStripFaceCount > 2)
                         {
                             int nShared0, nShared1;
                             GetSharedVertices(strip->m_faces[2], &tFirstFace, &nShared0, &nShared1);
                             if ( (nShared0 == tFirstFace.m_v1) && (nShared1 == -1) )
                             {
                                 SWAP(tFirstFace.m_v1, tFirstFace.m_v2);
                             }
                         }
                     }
                         
                     // Check CW/CCW ordering
                     if (bWantsCW == IsCW(strip->m_faces[0], tFirstFace.m_v0, tFirstFace.m_v1))
                     {
                         //I like this one!
                         bestIndex = i;
                     }
                 }
             }
             
             if(bestNumHits == -1.0f)
                 break;
             tempStrips2[bestIndex]->visited = true;
             UpdateCacheStrip(vcache, tempStrips2[bestIndex]);
             outStrips.push_back(tempStrips2[bestIndex]);
             bWantsCW = (tempStrips2[bestIndex]->m_faces.size() % 2 == 0) ? bWantsCW : !bWantsCW;
         }
         
         delete vcache;  
     }
 }
 
 
 // UpdateCacheStrip()
 //
 // Updates the input vertex cache with this strip's vertices
 //
 void NvStripifier::UpdateCacheStrip(VertexCache* vcache, NvStripInfo* strip)
 {
     for(size_t i = 0; i < strip->m_faces.size(); ++i)
     {
         if(!vcache->InCache(strip->m_faces[i]->m_v0))
             vcache->AddEntry(strip->m_faces[i]->m_v0);
         
         if(!vcache->InCache(strip->m_faces[i]->m_v1))
             vcache->AddEntry(strip->m_faces[i]->m_v1);
         
         if(!vcache->InCache(strip->m_faces[i]->m_v2))
             vcache->AddEntry(strip->m_faces[i]->m_v2);
     }
 }
 
 // UpdateCacheFace()
 //
 // Updates the input vertex cache with this face's vertices
 //
 void NvStripifier::UpdateCacheFace(VertexCache* vcache, NvFaceInfo* face)
 {
     if(!vcache->InCache(face->m_v0))
         vcache->AddEntry(face->m_v0);
         
     if(!vcache->InCache(face->m_v1))
         vcache->AddEntry(face->m_v1);
         
     if(!vcache->InCache(face->m_v2))
         vcache->AddEntry(face->m_v2);
 }
 
 
 // CalcNumHitsStrip()
 //
 // returns the number of cache hits per face in the strip
 //
 float NvStripifier::CalcNumHitsStrip(VertexCache* vcache, NvStripInfo* strip)
 {
     int numHits = 0;
     int numFaces = 0;
     
     for(size_t i = 0; i < strip->m_faces.size(); i++)
     {
         if(vcache->InCache(strip->m_faces[i]->m_v0))
             ++numHits;
         
         if(vcache->InCache(strip->m_faces[i]->m_v1))
             ++numHits;
         
         if(vcache->InCache(strip->m_faces[i]->m_v2))
             ++numHits;
         
         numFaces++;
     }
     
     return ((float)numHits / (float)numFaces);
 }
 
 
 // CalcNumHitsFace()
 //
 // returns the number of cache hits in the face
 //
 int NvStripifier::CalcNumHitsFace(VertexCache* vcache, NvFaceInfo* face)
 {
     int numHits = 0;
 
     if(vcache->InCache(face->m_v0))
         numHits++;
         
     if(vcache->InCache(face->m_v1))
         numHits++;
         
     if(vcache->InCache(face->m_v2))
         numHits++;
         
     return numHits;
 }
 
 
 // NumNeighbors()
 //
 // Returns the number of neighbors that this face has
 //
 int NvStripifier::NumNeighbors(NvFaceInfo* face, NvEdgeInfoVec& edgeInfoVec)
 {
     int numNeighbors = 0;
     
     if(FindOtherFace(edgeInfoVec, face->m_v0, face->m_v1, face) != NULL)
     {
         numNeighbors++;
     }
     
     if(FindOtherFace(edgeInfoVec, face->m_v1, face->m_v2, face) != NULL)
     {
         numNeighbors++;
     }
     
     if(FindOtherFace(edgeInfoVec, face->m_v2, face->m_v0, face) != NULL)
     {
         numNeighbors++;
     }
     
     return numNeighbors;
 }
 
 
 // AvgStripSize()
 //
 // Finds the average strip size of the input vector of strips
 //
 float NvStripifier::AvgStripSize(const NvStripInfoVec &strips){
     int sizeAccum = 0;
     int numStrips = strips.size();
     for (int i = 0; i < numStrips; i++){
         NvStripInfo *strip = strips[i];
         sizeAccum += strip->m_faces.size();
         sizeAccum -= strip->m_numDegenerates;
     }
     return ((float)sizeAccum) / ((float)numStrips);
 }
 
 
 // FindAllStrips()
 //
 // Does the stripification, puts output strips into vector allStrips
 //
 // Works by setting runnning a number of experiments in different areas of the mesh, and
 //  accepting the one which results in the longest strips.  It then accepts this, and moves
 //  on to a different area of the mesh.  We try to jump around the mesh some, to ensure that
 //  large open spans of strips get generated.
 //
 void NvStripifier::FindAllStrips(NvStripInfoVec &allStrips,
                                  NvFaceInfoVec &allFaceInfos,
                                  NvEdgeInfoVec &allEdgeInfos,
                                  int numSamples){
     // the experiments
     int experimentId = 0;
     int stripId      = 0;
     bool done        = false;
 
     int loopCtr = 0;
     
     while (!done)
     {
         loopCtr++;
         
         //
         // PHASE 1: Set up numSamples * numEdges experiments
         //
         NvStripInfoVec *experiments = new NvStripInfoVec [numSamples * 6];
         int experimentIndex = 0;
         std::set   <NvFaceInfo*>  resetPoints;
         for (int i = 0; i < numSamples; i++)
         {
             
             // Try to find another good reset point.
             // If there are none to be found, we are done
             NvFaceInfo *nextFace = FindGoodResetPoint(allFaceInfos, allEdgeInfos);
             if (nextFace == NULL){
                 done = true;
                 break;
             }
             // If we have already evaluated starting at this face in this slew
             // of experiments, then skip going any further
             else if (resetPoints.find(nextFace) != resetPoints.end()){
                 continue;
             }
             
             // trying it now...
             resetPoints.insert(nextFace);
             
             // otherwise, we shall now try experiments for starting on the 01,12, and 20 edges
             assert(nextFace->m_stripId < 0);
             
             // build the strip off of this face's 0-1 edge
             NvEdgeInfo *edge01 = FindEdgeInfo(allEdgeInfos, nextFace->m_v0, nextFace->m_v1);
             NvStripInfo *strip01 = new NvStripInfo(NvStripStartInfo(nextFace, edge01, true), stripId++, experimentId++);
             experiments[experimentIndex++].push_back(strip01);
             
             // build the strip off of this face's 1-0 edge
             NvEdgeInfo *edge10 = FindEdgeInfo(allEdgeInfos, nextFace->m_v0, nextFace->m_v1);
             NvStripInfo *strip10 = new NvStripInfo(NvStripStartInfo(nextFace, edge10, false), stripId++, experimentId++);
             experiments[experimentIndex++].push_back(strip10);
             
             // build the strip off of this face's 1-2 edge
             NvEdgeInfo *edge12 = FindEdgeInfo(allEdgeInfos, nextFace->m_v1, nextFace->m_v2);
             NvStripInfo *strip12 = new NvStripInfo(NvStripStartInfo(nextFace, edge12, true), stripId++, experimentId++);
             experiments[experimentIndex++].push_back(strip12);
             
             // build the strip off of this face's 2-1 edge
             NvEdgeInfo *edge21 = FindEdgeInfo(allEdgeInfos, nextFace->m_v1, nextFace->m_v2);
             NvStripInfo *strip21 = new NvStripInfo(NvStripStartInfo(nextFace, edge21, false), stripId++, experimentId++);
             experiments[experimentIndex++].push_back(strip21);
             
             // build the strip off of this face's 2-0 edge
             NvEdgeInfo *edge20 = FindEdgeInfo(allEdgeInfos, nextFace->m_v2, nextFace->m_v0);
             NvStripInfo *strip20 = new NvStripInfo(NvStripStartInfo(nextFace, edge20, true), stripId++, experimentId++);
             experiments[experimentIndex++].push_back(strip20);
             
             // build the strip off of this face's 0-2 edge
             NvEdgeInfo *edge02 = FindEdgeInfo(allEdgeInfos, nextFace->m_v2, nextFace->m_v0);
             NvStripInfo *strip02 = new NvStripInfo(NvStripStartInfo(nextFace, edge02, false), stripId++, experimentId++);
             experiments[experimentIndex++].push_back(strip02);
         }
         
         //
         // PHASE 2: Iterate through that we setup in the last phase
         // and really build each of the strips and strips that follow to see how
         // far we get
         //
         int numExperiments = experimentIndex;
         for (int i = 0; i < numExperiments; i++){
             
             // get the strip set
             
             // build the first strip of the list
             experiments[i][0]->Build(allEdgeInfos, allFaceInfos);
             int experimentId = experiments[i][0]->m_experimentId;
             
             NvStripInfo *stripIter = experiments[i][0];
             NvStripStartInfo startInfo(NULL, NULL, false);
             while (FindTraversal(allFaceInfos, allEdgeInfos, stripIter, startInfo)){
                 
                 // create the new strip info
                 stripIter = new NvStripInfo(startInfo, stripId++, experimentId);
                 
                 // build the next strip
                 stripIter->Build(allEdgeInfos, allFaceInfos);
                 
                 // add it to the list
                 experiments[i].push_back(stripIter);
             }
         }
         
         //
         // Phase 3: Find the experiment that has the most promise
         //
         int bestIndex = 0;
         double bestValue = 0;
         for (int i = 0; i < numExperiments; i++)
         {
             const float avgStripSizeWeight = 1.0f;
             //const float numTrisWeight      = 0.0f;
             const float numStripsWeight    = 0.0f;
             float avgStripSize = AvgStripSize(experiments[i]);
             float numStrips    = (float) experiments[i].size();
             float value        = avgStripSize * avgStripSizeWeight + (numStrips * numStripsWeight);
             //float value = 1.f / numStrips;
             //float value = numStrips * avgStripSize;
                 
             if (value > bestValue)
             {
                 bestValue = value;
                 bestIndex = i;
             }
         }
 
         //
         // Phase 4: commit the best experiment of the bunch
         //
         CommitStrips(allStrips, experiments[bestIndex]);
         
         // and destroy all of the others
         for (int i = 0; i < numExperiments; i++)
         {
             if (i != bestIndex)
             {
                 int numStrips = experiments[i].size();
                 for (int j = 0; j < numStrips; j++)
                 {
                     NvStripInfo* currStrip = experiments[i][j];
                     //delete all bogus faces in the experiments
                     for (size_t k = 0; k < currStrip->m_faces.size(); ++k)
                     {
                         if(currStrip->m_faces[k]->m_bIsFake)
                         {
                             delete currStrip->m_faces[k], currStrip->m_faces[k] = NULL;
                         }
                     }
                     delete currStrip, currStrip = NULL, experiments[i][j] = NULL;
                 }
             }
         }
         
         // delete the array that we used for all experiments
         delete [] experiments;
   }
 }
 
 
 // CountRemainingTris()
 //
 // This will count the number of triangles left in the
 // strip list starting at iter and finishing up at end
 //
 int NvStripifier::CountRemainingTris(std::list<NvStripInfo*>::iterator iter,
                                             std::list<NvStripInfo*>::iterator  end){
     int count = 0;
     while (iter != end){
         count += (*iter)->m_faces.size();
         iter++;
     }
     return count;
 }
 

